package 系统复习.面试题.滑动窗口;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个字符串 s 和一个整数 k ，请你找出 至多 包含 k 个 不同 字符的最长子串，并返回该子串的长度。
 */
public class L340 {

    public int lengthOfLongestSubstringKDistinct(String s, int k) {

        Map<Character, Integer> map = new HashMap<>();
        int max = 0;
        for (int l = 0, r = 0; r < s.length(); r++) {
            char character = s.charAt(r);
            if (!map.containsKey(character)) {
                map.put(character, 1);
            } else {
                map.put(character, map.get(character) + 1);
            }

            while (map.size() > k) {
                char leftChar = s.charAt(l++);
                int value = map.get(leftChar) - 1;
                if(value == 0) {
                    map.remove(leftChar);
                }else {
                    map.put(leftChar, value);
                }
            }
            max = Math.max(max, r - l + 1);
        }
        return max;
    }

    public static void main(String[] args) {
        L340 l340 = new L340();
        System.out.println(l340.lengthOfLongestSubstringKDistinct("eceba", 2));
        System.out.println(l340.lengthOfLongestSubstringKDistinct("aa", 2));
    }
}
